
/*
 * Pathfinder.java
 *
 * Created on March 17, 2007, 7:09 PM
 *
 * Copyright 2008 David D. Emory
 * 
 * This file is part of Five Points. See <http://www.fpdev.org> for
 * additional information regarding the project.
 * 
 * Five Points is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * Five Points is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Five Points.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.fpdev.core.algo.path;

import org.fpdev.core.routenet.RNode;
import org.fpdev.core.routenet.RLinkBoard;
import org.fpdev.core.routenet.RLinkAlight;
import org.fpdev.core.routenet.RLink;
import org.fpdev.core.*;
import org.fpdev.core.algo.RouteDLS;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import org.fpdev.core.algo.DepthLimitedSearch;
import org.fpdev.core.algo.ListenableDijkstra;
import org.fpdev.core.basenet.*;
import org.fpdev.core.transit.*;
import org.fpdev.core.trip.*;
import org.fpdev.util.FPUtil;

/**
 * The primary class for the path-building engine.
 * 
 * @author demory
 */
public class Pathfinder {

  private FPEngine engine_;

  // current trip parameters
  private BNode startBNode_,  endBNode_;
  private CalendarService service_;
  private TimeMode timeMode_;
  private int tripType_,  time_, walkLimit_;
  private double nmSpeedFPS_;
  private double bikeTypeFactor_, bikeTopFactor_;
  private Scenario scen_;

  // flags indicating whether start/end is a RouteNetwork node
  private boolean startOnRNet_, endOnRNet_;

  // depth-limited search instances for departure/arrival trip segments
  private RouteDLS depDLS_;
  private RouteDLS arrDLS_;

  // lookup tables for current sets of dynamacally-generated board/alight links
  // for the RouteNet. The keys are Strings of the format "FULLID@DLI", where:
  //   "FULLID" is the Full ID of the SubRoute being boarded/alighted
  //   "DLI" is the integer index of the SubRoute's direct-path access link 
  private Map<String, RLinkBoard> boardRLinks_;
  private Map<String, RLinkAlight> alightRLinks_;


  private RNode startRNode_,  endRNode_;
  private List<RLink> pathRLinks_;
  private SortedMap<Integer, SegmentList> pqTT_,  pqNT_;
  private Map<Integer, Integer> startTimesTT_,  startTimesNT_; // used by segListToTrip in arrive-by cases

  // three potential best trip results:
  //  bestNMTrip_: used in walk/bike only trips ("NM" = "non-motorized") 
  //  bestTripTT_: transit-based trip than minimizes travel time  
  //  bestTripNT_: transit-based trip than minimizes # of transfers
  private Trip bestNMTrip_,  bestTripTT_,  bestTripNT_;

  // text-based messages generated during search:
  private List<String> tripMsgs_;
  
  //
  private Set<String> validSubs_;

  public enum TimeMode { 
    DEPART_AT(1, "Depart At"),
    ARRIVE_BY(2, "Arrive By");

    private final int numCode_;
    private final String name_;

    TimeMode(int numCode, String name) {
      numCode_ = numCode; name_ = name;
    }

    public int getNumCode() { return numCode_; }

    public String getName() { return name_; }

  };
  //  public static final int DEPART_AT = 1;
  //  public static final int ARRIVE_BY = 2;

  // TODO: convert all of following to enum

  public static final int TRAVEL_TIME = 1;
  public static final int NUM_TRANSFERS = 2;
  public static final int WALK_DISTANCE = 3;

  public static final int WALK_TO_TRANSIT = 1;
  public static final int BIKE_TO_TRANSIT = 2;
  public static final int WALK_ONLY = 3;
  public static final int BIKE_ONLY = 4;

  public Pathfinder(FPEngine engine) {
    engine_ = engine;
  }

  public boolean findShortestTrip(Scenario scen, int tripType, int time, CalendarService service, TimeMode timeMode, double nmSpeedFPS, int walkLimit, BNode startNode, BNode endNode) {
    return findShortestTrip(scen, tripType, time, service, timeMode, nmSpeedFPS, walkLimit, 0, 0, startNode, endNode);
  }

  public boolean findShortestTrip(Scenario scen, int tripType, int time, CalendarService service, TimeMode timeMode, double nmSpeedFPS, int walkLimit, double bikeTypeFactor, double bikeTopFactor, BNode startNode, BNode endNode) {
    tripMsgs_ = new LinkedList<String>();
    scen_ = scen;
    tripType_ = tripType;
    time_ = time;
    timeMode_ = timeMode;
    service_ = service;
    walkLimit_ = walkLimit;
    nmSpeedFPS_ = nmSpeedFPS;
    bikeTypeFactor_ = bikeTypeFactor;
    bikeTopFactor_ = bikeTopFactor;

    // error-checking for bike factors:
    if (bikeTypeFactor < 0) {
      bikeTypeFactor = 0;
    }
    if (bikeTopFactor < 0) {
      bikeTopFactor = 0;
    }
    if (bikeTypeFactor + bikeTopFactor > 1) {
      System.out.println("  error - invalid bike type/top factors: " + bikeTypeFactor + "/" + bikeTopFactor);
      bikeTypeFactor = bikeTopFactor = 0;
    }

    initValidSubs();

    if (startNode.isAddressNode()) {
      startNode = ((BNodeAddress) startNode).getNearEndNode();
    }
    if (endNode.isAddressNode()) {
      endNode = ((BNodeAddress) endNode).getNearEndNode();
    }
    startBNode_ = startNode;
    endBNode_ = endNode;

    switch (tripType) {
      case WALK_TO_TRANSIT:
        engine_.getBaseNet().getGraph().setWeightMode(BaseNetGraph.WEIGHT_WALK, scen_);
        return findWalkToTransitTrip(); //time, day, timeMode, nmSpeedFPS, walkLimit, startNode, endNode);
      case BIKE_TO_TRANSIT:
        engine_.getBaseNet().getGraph().setWeightMode(BaseNetGraph.WEIGHT_BIKE, scen_);
        engine_.getBaseNet().getGraph().setBikeFactors(bikeTypeFactor, bikeTopFactor);
        return findWalkToTransitTrip(); //time, day, timeMode, nmSpeedFPS, walkLimit, startNode, endNode);
      case WALK_ONLY:
        return findWalkOnlyTrip(); //time, timeMode, nmSpeedFPS, startNode, endNode);
      case BIKE_ONLY:
        return findBikeOnlyTrip(); //time, timeMode, nmSpeedFPS, bikeTypeFactor, bikeTopFactor, startNode, endNode);
    }

    return false;
  }

  /**
   * Initializes the valid subroutes field 
   */
  private void initValidSubs() {
    validSubs_ = new HashSet<String>();
    Set<String> strippedRteIDs = new HashSet<String>();

    for(Route rte : engine_.getRoutes().getCollection(scen_, true)) {
      String strippedID = rte.getStrippedCombinedID();
      if (strippedRteIDs.contains(strippedID)) continue;
      strippedRteIDs.add(strippedID);
      for(SubRoute sub : rte.getSubRoutes())
        validSubs_.add(sub.getMasterID());
    }
  }

  public boolean findWalkToTransitTrip() { //int time, Timetable.DayOfWeek day, int timeMode, double walkSpeedFPS, int walkLimit, BNode startNode, BNode endNode) {
    if (engine_.getRouteNetwork() == null) {
      tripMsgs_.add("Route network not initialized");
      return false;
    }
    bestTripTT_ = null;

    pqTT_ = new TreeMap<Integer, SegmentList>();
    pqNT_ = new TreeMap<Integer, SegmentList>();

    boardRLinks_ = new HashMap<String, RLinkBoard>();
    alightRLinks_ = new HashMap<String, RLinkAlight>();

    if (timeMode_ == TimeMode.ARRIVE_BY) {
      startTimesTT_ = new HashMap<Integer, Integer>();
      startTimesNT_ = new HashMap<Integer, Integer>();
    }
    engine_.getRouteNetwork().clearPathSearchElements();


    startOnRNet_ = engine_.getRouteNetwork().isOnNetwork(startBNode_);
    endOnRNet_ = engine_.getRouteNetwork().isOnNetwork(endBNode_);

    startRNode_ = startOnRNet_ ? engine_.getRouteNetwork().getStartRouteNode(startBNode_) : engine_.getRouteNetwork().initStartNode(startBNode_);
    if (tripType_ == WALK_TO_TRANSIT) {
      depDLS_ = new RouteDLS(engine_, DepthLimitedSearch.TYPE_WALK, walkLimit_, RouteDLS.MODE_DEPARTING, RouteDLS.OPTION_RECORDVISITED);
    }
    if (tripType_ == BIKE_TO_TRANSIT) {
      depDLS_ = new RouteDLS(engine_, DepthLimitedSearch.TYPE_BIKE, walkLimit_, RouteDLS.MODE_DEPARTING, RouteDLS.OPTION_RECORDVISITED);
    }

    depDLS_.execute(startBNode_);

    endRNode_ = endOnRNet_ ? engine_.getRouteNetwork().getEndRouteNode(endBNode_) : engine_.getRouteNetwork().initEndNode(endBNode_);


    if (tripType_ == WALK_TO_TRANSIT) {
      arrDLS_ = new RouteDLS(engine_, DepthLimitedSearch.TYPE_WALK, walkLimit_, RouteDLS.MODE_ARRIVING, RouteDLS.OPTION_CHECKVISITED);
    }
    if (tripType_ == BIKE_TO_TRANSIT) {
      engine_.getBaseNet().getGraph().setIsReverse(true);
      //System.out.println("set main rev = "+engine_.getBaseNet().getGraph().getIsReverse());
      arrDLS_ = new RouteDLS(engine_, DepthLimitedSearch.TYPE_BIKE, walkLimit_, RouteDLS.MODE_ARRIVING, RouteDLS.OPTION_CHECKVISITED);
    }
    arrDLS_.setRecordedNodes(depDLS_.getRecordedNodes());
    arrDLS_.execute(endBNode_);

    if (arrDLS_.getIsectNode() != null) {
      createNonMotTransitTrip(time_, startBNode_, endBNode_);
    }
    prepareRouteNetForSearch(startBNode_, endBNode_);

    if (depDLS_.getSRILookup().size() > 0 && arrDLS_.getSRILookup().size() > 0) {
      runTripScan(time_);
      findOneSeatTrips(time_, startBNode_, endBNode_);
    }
    boolean successTT = false, successNT = false;

    if (pqTT_.size() > 0) {
      SegmentList segList = pqTT_.get(pqTT_.firstKey());
      try {
        bestTripTT_ = segmentListToTrip(segList.getSegments(),
                timeMode_ == TimeMode.DEPART_AT ? time_ : startTimesTT_.get(segList.getID()),
                Trip.Type.TRAVEL_TIME);
        successTT = true;
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    if (pqNT_.size() > 0) {
      SegmentList segList = pqNT_.get(pqNT_.firstKey());
      try {
        bestTripNT_ = segmentListToTrip(segList.getSegments(),
                timeMode_ == TimeMode.DEPART_AT ? time_ : startTimesNT_.get(segList.getID()),
                Trip.Type.NUM_TRANSFERS);
        successNT = true;
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    return successTT & successNT;
  }

  public boolean findWalkOnlyTrip() { // int time, int timeMode, double walkSpeedFPS, BNode startNode, BNode endNode) {
    engine_.getBaseNet().getGraph().setWeightMode(BaseNetGraph.WEIGHT_WALK, scen_);
    ListenableDijkstra dsp = engine_.getBaseNet().getDijkstra(startBNode_, endBNode_);
    if (dsp == null || dsp.getPathLength() >= 100000000) {
      tripMsgs_.add("No walkable path found between specified locations");
      return false;
    }
    RNWalkSegment segment = new RNWalkSegment(dsp.getPathEdgeList().iterator(), startBNode_);
    List<RNSegment> segList = new LinkedList<RNSegment>();
    segList.add(segment);
    double startTime = (timeMode_ == TimeMode.DEPART_AT) ? time_ : time_ - dsp.getPathLength() / nmSpeedFPS_;
    bestNMTrip_ = segmentListToTrip(segList, (int) startTime, Trip.Type.NON_MOTORIZED);
    return true;
  }

  public boolean findBikeOnlyTrip() { // int time, int timeMode, double walkSpeedFPS, double bikeTypeFactor, double bikeTopFactor, BNode startNode, BNode endNode) {
    engine_.getBaseNet().getGraph().setWeightMode(BaseNetGraph.WEIGHT_BIKE, scen_);
    engine_.getBaseNet().getGraph().setBikeFactors(bikeTypeFactor_, bikeTopFactor_);
    ListenableDijkstra dsp = engine_.getBaseNet().getDijkstra(startBNode_, endBNode_);
    if (dsp == null || dsp.getPathLength() >= 100000000) {
      tripMsgs_.add("No bikeable path found between specified locations");
      return false;
    }
    RNBikeSegment segment = new RNBikeSegment(dsp.getPathEdgeList().iterator(), startBNode_);
    List<RNSegment> segList = new LinkedList<RNSegment>();
    segList.add(segment);
    double startTime = (timeMode_ == TimeMode.DEPART_AT) ? time_ : time_ - dsp.getPathLength() / nmSpeedFPS_;
    bestNMTrip_ = segmentListToTrip(segList, (int) startTime, Trip.Type.NON_MOTORIZED);
    //System.out.println("found bike trip, len = "+dsp.getPathEdgeList().size());

    return true;
  }

  public Trip getBestTripNM() {
    return bestNMTrip_;
  }

  public Trip getBestTripTT() {
    return bestTripTT_;
  }

  public Trip getBestTripNT() {
    return bestTripNT_;
  }

  public Iterator<String> getMessages() {
    return tripMsgs_.iterator();
  }

  private Trip segmentListToTrip(List<RNSegment> segments, int startTime, Trip.Type type) {
    //System.out.println("sLTT startTime="+CUtil.sTimeToStr(startTime));
    Trip trip = new Trip(type, startBNode_);


    int i = 0, len = segments.size(), arrTime = startTime;
    while (i < len) {
      RNSegment seg = segments.get(i);
      if ((seg.getType() == RNSegment.RNS_WALK || seg.getType() == RNSegment.RNS_BIKE) && ((RNNonMotSegment) seg).getLinks().size() > 0) {

        NonMotorizedTripItem nmtrip = this.nmSegmentToTrip(seg, arrTime);
        if (nmtrip.subItemCount() > 0) {
          trip.addItem(nmtrip);
          arrTime += nmtrip.getLenSec();
        }

      } else if (seg.getType() == RNSegment.RNS_TRANSIT) {
        RNTransitSegment tseg = (RNTransitSegment) seg;
        String id = tseg.getID();
        int onDLI = tseg.getOnDLI();
        while (i + 1 < len &&
                segments.get(i + 1).getType() == RNSegment.RNS_TRANSIT &&
                id.compareTo(((RNTransitSegment) segments.get(i + 1)).getID()) == 0) {
          i++;
        }
        int offDLI = ((RNTransitSegment) segments.get(i)).getOffDLI();
        TransitTripItem ttrip = new TransitTripItem(tseg.getSubRoute(), service_, tseg.getRun(), onDLI, offDLI);
        int onTime = ttrip.getStart();
        int offTime = ttrip.getEnd();
        trip.addItem(new WaitItem(ttrip.getBoardNode(), arrTime, onTime));
        trip.addItem(ttrip);
        arrTime = offTime;

      }
      i++;
    }

    // add end-of-trip idle time for arrive-by queries
    if (timeMode_ == TimeMode.ARRIVE_BY) {
      trip.addItem(new WaitItem(endBNode_, trip.getEnd(), time_));
    }

    //engine_.msg("created trip item, len="+trip.itemCount());
    return trip;
  }

  public NonMotorizedTripItem bikeLinksToTrip(String pathStr) {
    String arr[] = pathStr.split(",");
    BNode startNode = engine_.getNodeFromID(new Integer(arr[0]));
    List<BLink> links = new LinkedList<BLink>();
    for (int i = 1; i < arr.length; i++) {
      if(FPUtil.isInteger(arr[i]))
        links.add(engine_.getLinkFromID(new Integer(arr[i])));
    }
    RNBikeSegment segment = new RNBikeSegment(links.iterator(), startNode);
    return nmSegmentToTrip(segment, 0);
  }

  private NonMotorizedTripItem nmSegmentToTrip(RNSegment seg, int arrTime) {
    //System.out.println("nmStT type "+seg.getType());
    NonMotorizedTripItem nmtrip = (seg.getType() == RNSegment.RNS_WALK) ? new WalkTripItem() : new BikeTripItem();
    //System.out.println(" created "+nmtrip.getItemName());
    List<BLink> links = ((RNNonMotSegment) seg).getLinks();
    BNode fNode = ((RNNonMotSegment) seg).getStartNode();
    //System.out.println("startNode: "+fNode.getID()+" "+fNode.getDisplayName(engine_.getGraph()));
    Iterator<BLink> testLinks = links.iterator();
    while (testLinks.hasNext()) {
      BLink link = testLinks.next();
    //System.out.println("link: "+link.getID()+" "+link.getDisplayName());

    }
    int nmli = 0; // non-mot link index
    int nmArrTime = arrTime, fullPathLenSec = 0;
    while (nmli < links.size()) {

      String name = ""; //links.get(wli).getDisplayName();
      name = FPUtil.standardizeStreetName(name);

      Path path = new Path(engine_);
      BLink link = links.get(nmli);
      if (tripType_ == WALK_TO_TRANSIT || tripType_ == BIKE_TO_TRANSIT) {
        while (link.isStation() && nmli + 1 < links.size()) {
          fNode = engine_.getBaseNet().opposite(fNode, link);
          link = links.get(nmli + 1);
          nmli++;
        }
      }
      int pathLenFt = 0;
      if (nmli < links.size() && (tripType_ == WALK_ONLY || tripType_ == BIKE_ONLY || !link.isStation())) {
        path.addDirectedFirstLink(link, fNode);
        pathLenFt += link.getLengthFeet();
        name = FPUtil.standardizeStreetName(links.get(nmli).getDisplayName());
      }
      //System.out.println(" fnode: "+fNode.getID()+" link: "+link.getID());
      fNode = engine_.getBaseNet().opposite(fNode, link); //(CNode) graph_.opposite(fNode.getVertex(), link.getEdge()).element();
      while (nmli + 1 < links.size() &&
              name.compareTo(FPUtil.standardizeStreetName(links.get(nmli + 1).getDisplayName())) == 0) {
        link = links.get(nmli + 1);
        if (tripType_ == WALK_ONLY || tripType_ == BIKE_ONLY || !link.isStation()) {
          path.addToEnd(link);
          pathLenFt += link.getLengthFeet();
        }
        //System.out.println("  fnode: "+fNode.getID()+" link: "+link.getID());
        fNode = engine_.getBaseNet().opposite(fNode, link); //(CNode) graph_.opposite(fNode.getVertex(), link.getEdge()).element();          
        nmli++;
      }
      double pathCostSecD = (double) pathLenFt / nmSpeedFPS_;
      int pathCostSec = (int) pathCostSecD;
      if (path.linkCount() > 0) {
        nmtrip.newSubtrip(path, nmArrTime, nmArrTime + pathCostSec);
      //System.out.println(" newSubTrip path len = "+path.linkCount());
      }
      nmArrTime += pathCostSec;
      fullPathLenSec += pathCostSec;
      nmli++;
    }
    nmtrip.setLenSec(fullPathLenSec);
    //if(nmtrip.subItemCount() > 0) trip.addItem(nmtrip);
    //arrTime += fullPathLenSec;
    return nmtrip;
  }

  private void createNonMotTransitTrip(int time, BNode startNode, BNode endNode) {
    //System.out.println("WALK TRIP");
    List<BLink> walkLinks = new LinkedList<BLink>();
    BNode isect = arrDLS_.getIsectNode();
    BNode curNode = isect;
    int dist = 0;
    while (curNode != startNode) {
      BLink link = depDLS_.getParentLink(curNode);
      walkLinks.add(0, link);
      dist += link.getLengthFeet();
      curNode = engine_.getBaseNet().opposite(curNode, link);
    }
    curNode = isect;
    while (curNode != endNode) {
      BLink link = arrDLS_.getParentLink(curNode);
      walkLinks.add(link);
      dist += link.getLengthFeet();
      curNode = engine_.getBaseNet().opposite(curNode, link);
    }
    List<RNSegment> segments = new LinkedList<RNSegment>();
    if (tripType_ == WALK_TO_TRANSIT) {
      segments.add(new RNWalkSegment(walkLinks, startNode));
    }
    if (tripType_ == BIKE_TO_TRANSIT) {
      segments.add(new RNBikeSegment(walkLinks, startNode));
    }
    double walkTime = dist / nmSpeedFPS_;
    //System.out.println("walk time: "+CUtil.elapsedTimeStr((int) walkTime));
    SegmentList segList = new SegmentList(segments);

    pqTT_.put(new Integer((int) walkTime), segList);
    pqNT_.put(new Integer(segList.countTransfers() * 1000000 + (int) walkTime), segList);

    if (timeMode_ == TimeMode.ARRIVE_BY) {
      int startTime = (int) (time - walkTime);
      //System.out.println("walk start time="+CUtil.sTimeToStr(startTime));
      startTimesTT_.put(new Integer(segList.getID()), new Integer(startTime));
      startTimesNT_.put(new Integer(segList.getID()), new Integer(startTime));
    }
  }

  private void findOneSeatTrips(int time, BNode startNode, BNode endNode) {

    // populate dictionary of origin outbound SRIs
    Map<String, SubRouteInfo> startSRIs = new HashMap<String, SubRouteInfo>();//HashtableDictionary(new ObjectHashComparator());
    if (startOnRNet_) {
      Iterator<RLink> outLinks = engine_.getRouteNetwork().outLinks(startRNode_); //getRGraph().incidentEdges(startRNode_.getVertex(), EdgeDirection.OUT);
      while (outLinks.hasNext()) {
        RLink rlink = outLinks.next();
        if (!validSubs_.contains(rlink.getSubRoute().getMasterID())) {
          continue;
        }
        startSRIs.put(rlink.getSubRoute().getFullID(), new SubRouteInfo(rlink.getSubRoute(), rlink.getStartDLI()));
      }
    } else {

      Iterator<SubRouteInfo> depSRIs = depDLS_.getSRILookup().values().iterator();
      while (depSRIs.hasNext()) {
        SubRouteInfo sri = depSRIs.next();
        if (!validSubs_.contains(sri.getSubRoute().getMasterID())) {
          continue;
        }
        startSRIs.put(sri.getSubRoute().getFullID(), sri);
      }
    }

    // iterate through destination inbound SRIs 
    if (endOnRNet_) {
      Iterator<RLink> inLinks = engine_.getRouteNetwork().inLinks(endRNode_); //getRGraph().incidentEdges(endRNode_.getVertex(), EdgeDirection.IN);
      while (inLinks.hasNext()) {
        RLink rlink = inLinks.next();
        if (!validSubs_.contains(rlink.getSubRoute().getMasterID())) {
          continue;
        }
        SubRouteInfo startSRI = startSRIs.get(rlink.getSubRoute().getFullID());
        if (startSRI != null && startSRI.getDLI() <= rlink.getEndDLI()) {
          createOneSeatTrip(time, startSRI.getSubRoute(), startSRI.getDLI(), rlink.getEndDLI());
        }
      }
    } else {
      Iterator<SubRouteInfo> endSRIs = arrDLS_.getSRILookup().values().iterator();
      while (endSRIs.hasNext()) {
        SubRouteInfo endSRI = endSRIs.next();
        if (!validSubs_.contains(endSRI.getSubRoute().getMasterID())) {
          continue;
        }
        SubRouteInfo startSRI = startSRIs.get(endSRI.getSubRoute().getFullID());
        if (startSRI != null && startSRI.getDLI() <= endSRI.getDLI()) {
          createOneSeatTrip(time, startSRI.getSubRoute(), startSRI.getDLI(), endSRI.getDLI());
        }
      }
    }
  }

  public void createOneSeatTrip(int time, SubRoute sub, int startDLI, int endDLI) {
    switch (timeMode_) {
      case DEPART_AT:
        createOneSeatTripFW(time, sub, startDLI, endDLI);
        break;
      case ARRIVE_BY:
        createOneSeatTripBW(time, sub, startDLI, endDLI);
        break;
    }
  }

  public void createOneSeatTripFW(int startTime, SubRoute sub, int startDLI, int endDLI) {
    //System.out.println("one-seater fw: "+sub.getFullID()+" "+startDLI+" to "+endDLI);
    List<RNSegment> segments = new LinkedList<RNSegment>();
    int tripTime = 0;
    int arrTime = startTime;

    RLinkBoard bLink = boardRLinks_.get(sub.getFullID() + "@" + startDLI);
    if (bLink != null) { // add start walk segment, if necessary
      if (bLink.getAccessLinks().hasNext()) {
        if (tripType_ == WALK_TO_TRANSIT) {
          segments.add(new RNWalkSegment(bLink.getAccessLinks(), bLink.getWalkStart()));
        }
        if (tripType_ == BIKE_TO_TRANSIT) {
          segments.add(new RNBikeSegment(bLink.getAccessLinks(), bLink.getWalkStart()));
        }
        double walkTime = (double) bLink.getAccessLenFt() / nmSpeedFPS_;
        arrTime += (int) walkTime;
        tripTime += (int) walkTime;
      }
    }

    // add route segment
    int run = sub.getNextRun(service_, arrTime, startDLI);
    if (run == 0) {
      return;
    } // trip not possible
    int rteTime = (sub.getTime(service_, run, endDLI + 1) - arrTime);
    tripTime += rteTime;
    //System.out.println(" - "+sub.getFullID()+" time: "+CUtil.elapsedTimeStr(rteTime));
    segments.add(new RNTransitSegment(sub, run, startDLI, endDLI));

    RLinkAlight aLink = alightRLinks_.get(sub.getFullID() + "@" + endDLI);

    if (aLink != null) { // add end walk segment, if necessary
      if (aLink.getAccessLinks().hasNext()) {
        if (tripType_ == WALK_TO_TRANSIT) {
          segments.add(new RNWalkSegment(aLink.getAccessLinks(), aLink.getWalkStart()));
        }
        if (tripType_ == BIKE_TO_TRANSIT) {
          segments.add(new RNBikeSegment(aLink.getAccessLinks(), aLink.getWalkStart()));
        }
        double walkTime = (double) aLink.getAccessLenFt() / nmSpeedFPS_;
        tripTime += (int) walkTime;
      }
    }

    SegmentList segList = new SegmentList(segments);
    pqTT_.put(new Integer(tripTime), segList);
    pqNT_.put(new Integer(segList.countTransfers() * 1000000 + tripTime), segList);

  }

  public void createOneSeatTripBW(int endTime, SubRoute sub, int startDLI, int endDLI) {
    //System.out.println("one-seater bw: "+sub.getFullID()+" "+startDLI+" to "+endDLI);
    List<RNSegment> segments = new LinkedList<RNSegment>();
    int tripTime = 0;
    int depTime = endTime;

    RLinkAlight aLink = alightRLinks_.get(sub.getFullID() + "@" + endDLI);
    if (aLink != null) { // add end walk segment, if necessary
      if (aLink.getAccessLinks().hasNext()) {
        if (tripType_ == WALK_TO_TRANSIT) {
          segments.add(new RNWalkSegment(aLink.getAccessLinks(), aLink.getWalkStart()));
        }
        if (tripType_ == BIKE_TO_TRANSIT) {
          segments.add(new RNBikeSegment(aLink.getAccessLinks(), aLink.getWalkStart()));
        }
        double walkTime = (double) aLink.getAccessLenFt() / nmSpeedFPS_;
        depTime -= (int) walkTime;
        tripTime += (int) walkTime;
      }
    }

    // add route segment
    int run = sub.getPrevRun(service_, depTime, endDLI);
    if (run == 0) {
      return;
    } // trip not possible
    int rteTime = (depTime - sub.getTime(service_, run, startDLI));
    tripTime += rteTime;
    //System.out.println(" - "+sub.getFullID()+" time: "+CUtil.elapsedTimeStr(rteTime));
    segments.add(0, new RNTransitSegment(sub, run, startDLI, endDLI));

    RLinkBoard bLink = boardRLinks_.get(sub.getFullID() + "@" + startDLI);
    if (bLink != null) { // add start walk segment, if necessary
      if (bLink.getAccessLinks().hasNext()) {
        if (tripType_ == WALK_TO_TRANSIT) {
          segments.add(0, new RNWalkSegment(bLink.getAccessLinks(), bLink.getWalkStart()));
        }
        if (tripType_ == BIKE_TO_TRANSIT) {
          segments.add(0, new RNBikeSegment(bLink.getAccessLinks(), bLink.getWalkStart()));
        }
        double walkTime = (double) bLink.getAccessLenFt() / nmSpeedFPS_;
        tripTime += (int) walkTime;
      }
    }

    SegmentList segList = new SegmentList(segments);
    pqTT_.put(new Integer(tripTime), segList);
    pqNT_.put(new Integer(segList.countTransfers() * 1000000 + tripTime), segList);
    startTimesTT_.put(new Integer(segList.getID()), new Integer(endTime - tripTime));
    startTimesNT_.put(new Integer(segList.getID()), new Integer(endTime - tripTime));
  }

  public void prepareRouteNetForSearch(BNode startNode, BNode endNode) {

    Iterator<SubRouteInfo> sris = depDLS_.getSRILookup().values().iterator();
    if (!sris.hasNext()) {
      tripMsgs_.add("Warning: No transit facilities found within " + FPUtil.distanceStr(walkLimit_) + " mi. walk of start location (" + startNode.getDisplayName(engine_.getBaseNet()) + "). Try higher walk radius.");
    }
    while (sris.hasNext()) {
      SubRouteInfo sri = sris.next();
      if (!validSubs_.contains(sri.getSubRoute().getMasterID())) {
        continue;
      }

      // build access path
      List<BLink> accessLinks = new LinkedList<BLink>(); //NodeSequence();
      BNode curNode = sri.getAccessNode();
      //System.out.println("bdLink for "+sri.getSubRoute().getFullID()+" /w accNode "+sri.getAccessNode().getID());
      while (curNode != startNode) {
        BLink link = depDLS_.getParentLink(curNode);
        //System.out.println("bt n="+curNode.getID()+" l="+link.getID());
        accessLinks.add(0, link);
        curNode = engine_.getBaseNet().opposite(curNode, link); // (CNode) graph_.opposite(curNode.getVertex(), link.getEdge()).element();
      }

      if (!startOnRNet_ || startNode != sri.getSubRoute().getPath().getDirectPath().fromNode(sri.getDLI())) { //accessLinks.size() > 0) {
        RLinkBoard bLink = engine_.getRouteNetwork().createBoardLink(startNode, sri.getSubRoute(), sri.getDLI(), accessLinks);
        //System.out.println(" - added, id="+bLink.getID()+" tcFW="+bLink.timeCostFW(time_, day_, nmSpeedFPS_, 0)); 
        boardRLinks_.put(sri.getSubRoute().getFullID() + "@" + sri.getDLI(), bLink);
      }
    }

    sris = arrDLS_.getSRILookup().values().iterator();
    if (!sris.hasNext()) {
      tripMsgs_.add("Warning: No transit facilities found within " + FPUtil.distanceStr(walkLimit_) + " walk of end location (" + endNode.getDisplayName(engine_.getBaseNet()) + "). Try higher walk radius.");
    }
    while (sris.hasNext()) {
      SubRouteInfo sri = sris.next();
      if (!validSubs_.contains(sri.getSubRoute().getMasterID())) {
        continue;
      }


      boolean debug = false; //sri.getSubRoute().getFullID().equals("2:EB");
      if (debug) {
        System.out.println("** considering alight: " + sri.getSubRoute().getFullID() + " @ " + sri.getDLI());
      }

      // build access path
      List<BLink> accessLinks = new LinkedList<BLink>(); //NodeSequence();
      BNode curNode = sri.getAccessNode();
      if (debug) {
        System.out.println("arr sub: " + sri.getSubRoute().getFullID());
      }
      while (curNode != endNode) {
        BLink link = arrDLS_.getParentLink(curNode);
        accessLinks.add(link);
        curNode = engine_.getBaseNet().opposite(curNode, link); //(CNode) graph_.opposite(curNode.getVertex(), link.getEdge()).element();
      }
      if (debug) {
        System.out.println(" al-#accLinks: " + accessLinks.size());
      }

      if (!endOnRNet_ || endNode != sri.getSubRoute().getPath().getDirectPath().toNode(sri.getDLI())) { //accessLinks.size() > 0) {
        if (debug) {
          System.out.println("new alight");
        }
        RLinkAlight aLink = engine_.getRouteNetwork().createAlightLink(endNode, sri.getSubRoute(), sri.getDLI(), accessLinks);
        if (debug) {
          System.out.println(" - alink " + aLink.getID());
        }
        if (debug) {
          System.out.println(" - endnode " + endNode.getID());
        }
        alightRLinks_.put(sri.getSubRoute().getFullID() + "@" + sri.getDLI(), aLink);
      }
    }

  //engine_.msg("prepared route net");
  }

  public List<RNSegment> convertRLinksToSegments() {
    Iterator<RLink> rLinks = pathRLinks_.iterator(); // .elements();
    List<RNSegment> segments = new LinkedList<RNSegment>();

    while (rLinks.hasNext()) {
      RLink link = rLinks.next();

      switch (link.getType()) {
        case RLink.RLINK_BOARD:
          if (tripType_ == Pathfinder.WALK_TO_TRANSIT) {
            segments.add(new RNWalkSegment(((RLinkBoard) link).getAccessLinks(), ((RLinkBoard) link).getWalkStart()));
          //System.out.println("new walk seg");
          } else if (tripType_ == Pathfinder.BIKE_TO_TRANSIT) {
            segments.add(new RNBikeSegment(((RLinkBoard) link).getAccessLinks(), ((RLinkBoard) link).getWalkStart()));
          //System.out.println("new bike seg");
          }
          segments.add(new RNTransitSegment(link.getSubRoute(), link.getLastRun(), link.getStartDLI(), link.getEndDLI()));
          break;
        case RLink.RLINK_SUBROUTE:
          //System.out.println("fDT: creating "+link.getSubRoute().getFullID()+" sub seg w/ run="+link.getLastRun());
          segments.add(new RNTransitSegment(link.getSubRoute(), link.getLastRun(), link.getStartDLI(), link.getEndDLI()));
          break;
        case RLink.RLINK_ALIGHT:
          segments.add(new RNTransitSegment(link.getSubRoute(), link.getLastRun(), link.getStartDLI(), link.getEndDLI()));
          if (tripType_ == Pathfinder.WALK_TO_TRANSIT && ((RLinkAlight) link).accessLinkCount() > 0) {
            segments.add(new RNWalkSegment(((RLinkAlight) link).getAccessLinks(), ((RLinkAlight) link).getWalkStart()));
          } else if (tripType_ == Pathfinder.BIKE_TO_TRANSIT && ((RLinkAlight) link).accessLinkCount() > 0) {
            segments.add(new RNBikeSegment(((RLinkAlight) link).getAccessLinks(), ((RLinkAlight) link).getWalkStart()));
          }
          break;
      }
    }
    return segments;
  }

  public List<RLink> getRouteDijkstraLinks() {
    return pathRLinks_;
  }

  public void runTripScan(int time) {
    int tripTime = 0, startTime = 0;
    List<Integer> runs = null;
    RouteScanner scanner = null;

    try {
      switch(timeMode_) {
        case DEPART_AT:
          scanner = new RouteScannerFW(engine_.getRouteNetwork(), validSubs_, startRNode_, endRNode_, time, service_, nmSpeedFPS_);
          break;
        case ARRIVE_BY:
          scanner = new RouteScannerBW(engine_.getRouteNetwork(), validSubs_, startRNode_, endRNode_, time, service_, nmSpeedFPS_);
          break;
      }
      scanner.execute();

    } catch (Exception e) {
      e.printStackTrace();
    }

    tripTime = scanner.getBestTimeTT();
    pathRLinks_ = scanner.getBestRLinksTT();
    startTime = scanner.getBestStartTimeTT();
    //runs = scanner.getBestRunsTT();

    //System.out.println("tripTime="+tripTime);
    if (tripTime <= 0 || tripTime >= 100000000) {
      tripMsgs_.add("Warning: No transit connection with 5 transfers or less found between start and end locations.");
      return;
    }

    applyRuns(startTime);

    // convert r-links to segments
    List<RNSegment> segments = convertRLinksToSegments();
    if (tripTime > 0) {
      //System.out.println("TT time: "+CUtil.elapsedTimeStr(tripTime));
      SegmentList segList = new SegmentList(segments);
      pqTT_.put(new Integer(tripTime), segList);
      if (timeMode_ == TimeMode.ARRIVE_BY) {
        startTimesTT_.put(new Integer(segList.getID()), new Integer(startTime));
      }
    }


    // Number of transfers

    tripTime = scanner.getBestTimeNT();
    pathRLinks_ = scanner.getBestRLinksNT();
    startTime = scanner.getBestStartTimeNT();
    //runs = scanner.getBestRunsNT();

    if (tripTime <= 0 || tripTime >= 100000000) {
      tripMsgs_.add("Warning: No transit connection with 5 transfers or less found between start and end locations.");
      return;
    }

    applyRuns(startTime);

    // convert r-links to segments
    segments = convertRLinksToSegments();
    if (tripTime > 0) {
      //System.out.println("NT time: "+CUtil.elapsedTimeStr(tripTime));
      SegmentList segList = new SegmentList(segments);
      pqNT_.put(new Integer(segList.countTransfers() * 1000000 + tripTime), segList);
      if (timeMode_ == TimeMode.ARRIVE_BY) {
        startTimesNT_.put(new Integer(segList.getID()), new Integer(startTime));
      }
    }
  }

  private void applyRuns(int startTime) {
    int arrTime = startTime;
    //System.out.println("applying links");
    if (pathRLinks_.get(0).getType() == RLink.RLINK_BOARD) {
      double bsec = ((RLinkBoard) pathRLinks_.get(0)).getAccessLenFt() / nmSpeedFPS_;
      arrTime += bsec;
    //System.out.println(" alf="+((CRouteLinkBoard) pathRLinks_.get(0)).getAccessLenFt());
    //System.out.println(" bsec="+bsec); 
    //tripLenSec += bsec;
    }
    String prevSubID = pathRLinks_.get(0).getSubRoute().getFullID();
    //String linkStr = "";
    Iterator<RLink> rlIter = pathRLinks_.iterator();

    while (rlIter.hasNext()) {
      RLink rlink = rlIter.next();
      //linkStr += rlink.getID()+", ";
      //System.out.println(" rlink "+rlink.getID()+" arrTime "+CUtil.dtime(arrTime));
      int run = rlink.getSubRoute().getNextRun(service_, arrTime + (rlink.getSubRoute().getFullID().equals(prevSubID) ? 0 : 60), rlink.getStartDLI());
      if (run > 0) {
        int oldArrTime = arrTime;
        arrTime = rlink.getSubRoute().getTime(service_, run, rlink.getEndDLI() + 1);
        if (arrTime < oldArrTime) {
          System.out.println(" arrtime FUBAR");
        }
        //theseRuns.add(new Integer(run));
        rlink.setLastRun(run);
      //tripLenSec += rlink.timeCostFW();
      } else {
        //arrTime = tripLenSec = 100000000;
        break;
      }
      prevSubID = rlink.getSubRoute().getFullID();
    }
  //if(rlinks.get(rlinks.size()-1).getType() == CRouteLink.RLINK_ALIGHT)
  //  arrTime += ((CRouteLinkAlight) rlinks.get(rlinks.size()-1)).getAccessLenFt()/walkSpeedFPS_;

  }

  ////// Nested Helper Classes //////
  private interface RNSegment {

    public static final int RNS_WALK = 1;
    public static final int RNS_BIKE = 2;
    public static final int RNS_TRANSIT = 3;

    public int getType();
  }

  private abstract class RNNonMotSegment implements RNSegment {

    private List<BLink> links_;
    private BNode startNode_;

    public RNNonMotSegment(Iterator<BLink> links, BNode sNode) {
      links_ = new LinkedList<BLink>();
      while (links.hasNext()) {
        BLink link = links.next();
        links_.add(link);
      }
      startNode_ = sNode;
    }

    public RNNonMotSegment(List<BLink> links, BNode sNode) {
      //this(links.iterator(), sNode);
      links_ = links;
      startNode_ = sNode;
    }

    public List<BLink> getLinks() {
      return links_;
    }

    public BNode getStartNode() {
      return startNode_;
    }
  }

  private class RNWalkSegment extends RNNonMotSegment {

    public RNWalkSegment(Iterator<BLink> links, BNode sNode) {
      super(links, sNode);
    }

    public RNWalkSegment(List<BLink> links, BNode sNode) {
      super(links, sNode);
    }

    public int getType() {
      return RNS_WALK;
    }
  }

  private class RNBikeSegment extends RNNonMotSegment {

    public RNBikeSegment(Iterator<BLink> links, BNode sNode) {
      super(links, sNode);
    }

    public RNBikeSegment(List<BLink> links, BNode sNode) {
      super(links, sNode);
    }

    public int getType() {
      return RNS_BIKE;
    }
  }

  private class RNTransitSegment implements RNSegment {

    private SubRoute sub_;
    private int run_,  onDLI_,  offDLI_;

    public RNTransitSegment(SubRoute sub, int run, int onDLI, int offDLI) {
      sub_ = sub;
      run_ = run;
      onDLI_ = onDLI;
      offDLI_ = offDLI;
    //System.out.println("new RNTS: "+onDLI_+" to "+offDLI_);
    }

    public int getType() {
      return RNS_TRANSIT;
    }

    public SubRoute getSubRoute() {
      return sub_;
    }

    public int getRun() {
      return run_;
    }

    public int getOnDLI() {
      return onDLI_;
    }

    public int getOffDLI() {
      return offDLI_;
    }

    public String getID() {
      return sub_.getFullID() + "#" + run_;
    }
  }
  int slID_ = 0;

  public class SegmentList {

    private int id_; //, lenSec_;
    private List<RNSegment> segments_;

    public SegmentList(List<RNSegment> segs) {
      segments_ = segs;
      id_ = slID_;
      //lenSec_ = 0;
      slID_++;
    }

    public int getID() {
      return id_;
    }

    public List<RNSegment> getSegments() {
      return segments_;
    }

    private int countTransfers() {
      Iterator<RNSegment> segIter = segments_.iterator();
      int tsegs = 0;
      while (segIter.hasNext()) {
        if (segIter.next().getType() == RNSegment.RNS_TRANSIT) {
          tsegs++;
        }
      }
      return tsegs <= 0 ? 0 : tsegs - 1;
    }
  }
}
